#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include "data.h"
using namespace std;

//#define DEBUG 1

// 类型定义
// 信号
struct SIGNAL{
    uint32_t id;                // 初始基站id
    uint32_t curr;              // 当前卫星id
    vector<uint32_t> route;     // 路径点集
    vector<uint32_t> edges;     // 路径边集
};
// 顶点
struct VERTEX{
    uint32_t id;
    uint32_t type;            // 0: 发射基站 1: 卫星
    set<uint32_t> edges;      // 顶点的临边
    set<uint32_t> neighbors;  // 节点的邻居节点
    set<uint32_t> signals;    // 顶点上的信息
};
// 边
struct EDGE{
    uint32_t id;
    uint32_t v1;              // 相邻顶点1
    uint32_t v2;              // 相邻顶点2
    uint32_t dist;            // 边的长度
    uint32_t end_satellite;   // 经过边的信号接收卫星
};
// 子网
struct SubNetwork{
    uint32_t n;                 // 节点个数
    set<uint32_t> signals;      // 子网信号集合
    set<uint32_t> edges;        // 子网边集
    set<uint32_t> vertexs;      // 子网点集
    map<uint32_t, SIGNAL> id2signal;
    map<uint32_t, EDGE> id2edge;
    map<uint32_t, VERTEX> id2vertex;
};

// 全局变量
vector<uint32_t> ds_fa, ds_rank;  // 并查集

uint32_t gN, gE, gC, gD, gPS;     // 全局参数
vector<bool> id2type;             // 节点id的类型
vector<Edge> gedgeVec;

map<uint32_t, SIGNAL> signals;    // 全部信号集合
vector<VERTEX> vertexs;           // 全部顶点的集合
vector<EDGE> edges;               // 全部边的集合
vector<SubNetwork> networks;      // 子网网络集合

// 函数声明
void ds_init(uint32_t n);
uint32_t ds_find(uint32_t x);
void ds_union(uint32_t i, uint32_t j);

void parse_data(uint32_t N, uint32_t C, uint32_t D, uint32_t PS,
                const vector<bool>& typeVec, const vector<Edge>& edgeVec);
void divide_network(const vector<Edge>& edgeVec);
void basic_route(uint32_t nid);
void merge_signals(uint32_t nid);

/* 并查集初始化 */
void ds_init(uint32_t n){
    for (uint32_t i = 0; i < n; ++i){
        ds_fa.push_back(i);
        ds_rank.push_back(1);
    }
}

/* 并查集查找 */
uint32_t ds_find(uint32_t x) {
    return x == ds_fa[x] ? x : (ds_fa[x] = ds_find(ds_fa[x]));
}

/* 并查集合并 */
void ds_union(uint32_t i, uint32_t j) {
    uint32_t x = ds_find(i), y = ds_find(j);
    if (ds_rank[x] <= ds_rank[y]) ds_fa[x] = y;
    else ds_fa[y] = x;
    if (ds_rank[x] == ds_rank[y] && x != y) ds_rank[y]++;
}

/* 解析数据 */
void parse_data(uint32_t N, uint32_t C, uint32_t D, uint32_t PS,
                const vector<bool>& typeVec, const vector<Edge>& edgeVec){
    gN = N; gE = edgeVec.size(); gC = C; gD = D; gPS = PS;
    id2type = typeVec; gedgeVec = edgeVec;
    // 顶点和信号
    for(uint32_t i = 0; i<gN; ++i){
        VERTEX V;
        V.id = i;
        if(id2type[i]){
            V.type = 1;     // 卫星
        }else{
            V.type = 0;     // 发射基站
            V.signals.insert(i);

            SIGNAL S;
            S.id = i;
            S.curr = i;
            S.route.push_back(i);
            signals[i] = S;
        }
        vertexs.push_back(V);
    }
    // 边
    for(uint32_t i = 0; i<gE; ++i){
        EDGE E;
        E.id = i;
        E.v1 = edgeVec[i].send;
        E.v2 = edgeVec[i].recv;
        E.dist = edgeVec[i].dist;
        E.end_satellite = -1;
        edges.push_back(E);

        vertexs[E.v1].edges.insert(i);
        vertexs[E.v2].edges.insert(i);
        vertexs[E.v1].neighbors.insert(E.v2);
        vertexs[E.v2].neighbors.insert(E.v1);
    }
}

/* 划分子网 */
void divide_network(const vector<Edge>& edgeVec) {
    // 并查集——初始化、合并查找
    ds_init(gN);
    for (auto& edge:edgeVec) ds_union(edge.send, edge.recv);

    // 构建子网
    set<uint32_t> unique_fa = {ds_fa.begin(), ds_fa.end()};  // 合并后家族唯一编号
    uint32_t number = 0;
    for (uint32_t fid:unique_fa) {
        SubNetwork sn;
        uint32_t cnt = 0;
        for(auto& s:signals){
            if(ds_fa[s.first] == fid){
                sn.signals.insert(s.first);
                sn.id2signal[s.first] = s.second;
            }
        }
        for(auto& v:vertexs){
            if(ds_fa[v.id] == fid){
                sn.vertexs.insert(v.id);
                sn.id2vertex[v.id] = v;

                cnt++;
            }
        }
        for(auto& e:edges){
            if(ds_fa[e.v1] == fid || ds_fa[e.v2] == fid){
                sn.edges.insert(e.id);
                sn.id2edge[e.id] = e;
            }
        }
        sn.n = cnt;
        networks.push_back(sn);

        number++;
    }
}

/* 规划从基站到最近卫星的路线
 * 这一步可以得到整个问题的可行解
 * */
void basic_route(uint32_t nid) {
    auto& sub_network = networks[nid];
    for(uint32_t sid:sub_network.signals){
        auto& signal = sub_network.id2signal[sid];
        auto& vertex = sub_network.id2vertex[sid];
        // 获取信号的下一顶点和边
        uint32_t next_v = *(vertex.neighbors.begin());
        uint32_t next_e = *(vertex.edges.begin());
        for(auto item : vertex.neighbors){
            cout << item << endl;
        }
        // 更改信号当前位置和走过的路径
        signal.curr = next_v;
        signal.route.push_back(next_v);
        signal.edges.push_back(next_e);
        // 原顶点删除信号
        auto it = vertex.signals.find(sid);
        vertex.signals.erase(it);
        // 新顶点加入信号
        sub_network.id2vertex[next_v].signals.insert(sid);
        // 更改信号走过的边的属性
        auto& edge = sub_network.id2edge[next_e];
        edge.end_satellite = next_v;
    }
}

/* 合并子网中的信号
 * 在basic_route的基础上，满足约束条件进行合并
 * 进一步减小功耗成本
 * */
void merge_signals(uint32_t nid){

}

class Solution {
public:
    vector<Route> Plan(uint32_t N, uint32_t C, uint32_t D, uint32_t PS,
                       const vector<bool>& typeVec, const vector<Edge>& edgeVec)
    {
        // 解析数据
        parse_data(N, C, D, PS, typeVec, edgeVec);

        // 划分子网
        divide_network(edgeVec);

        // 对每一个子网做规划
        for(uint32_t i = 0; i<networks.size(); ++i){
            basic_route(i);  // 得到基础的可行解
            merge_signals(i);  // 进行进一步规划
        }

        // 返回结果
        vector<Route> retRouteVec(N);
        for(auto& sub_network : networks){
            for(uint32_t sid:sub_network.signals){
                retRouteVec[sid] = sub_network.id2signal[sid].route;
            }
        }
        return retRouteVec;
    }
};


int main(int argc, char *argv[])
{
#ifdef DEBUG
    freopen("../../judge/cases/Example.case", "r", stdin);
#endif
    uint32_t N;             // 表示所有卫星和发射基站的总数
    uint32_t E;             // 表示网络中可使用的路径总数
    uint32_t C;             // 表示路径距离L与功耗P的系数，传输功耗计算公式为：P=C*L
    uint32_t D;             // 表示全网最大路径长度限制。
    uint32_t PS;            // 表示接收卫星所需要的站点功耗
    vector<bool> typeVec;   // 下标为i的值代表ID为i的站点身份，卫星为true，发射基站为false
    vector<Edge> edgeVec;   // 包含E条边

    cin >> N >> E >> C >> D >> PS;
    typeVec = vector<bool>(N);
    for (uint32_t i = 0; i < N; i++) {
        bool type;
        cin >> type;
        typeVec[i] = type;
    }
    edgeVec = vector<Edge>(E);
    for (auto& edge : edgeVec) {
        cin >> edge.send >> edge.recv >> edge.dist;
    }

    Solution solution;
    vector<Route> retRouteVec = solution.Plan(N, C, D, PS, typeVec, edgeVec);
    for (const auto& route : retRouteVec) {
        for (const auto& siteId : route) {
            cout << siteId << " ";
        }
        cout << "\n";
    }
    return 0;
}

/*
 * 20210605
 [编译-结束]
-----------------------------------------
[用户程序-开始] 用例：Example
[用户程序-进行] 用例：Example 耗时=1s
[用户程序-结束] 用例：Example

[判题程序-开始] 用例：Example
[解析输出-开始] 用例：Example
[解析输出-结束] 用例：Example
[判题程序-结果] 用例：Example  功耗：30900  时间：2秒
[判题程序-结束] 用例：Example
-----------------------------------------
[用户程序-开始] 用例：TestData_24
[用户程序-进行] 用例：TestData_24 耗时=1s
[用户程序-结束] 用例：TestData_24

[判题程序-开始] 用例：TestData_24
[解析输出-开始] 用例：TestData_24
[解析输出-结束] 用例：TestData_24
[判题程序-结果] 用例：TestData_24  功耗：8819631  时间：2秒
[判题程序-结束] 用例：TestData_24
-----------------------------------------
[判题-成功] 最终分数：265515930
 */